package com.leetCode.StringDemo;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class StringLongestCommonPrefix {
    public static void main(String[] args) {
//        String[] strs = new String[]{"reflower","flow","flight"};
//        System.out.println(longestCommonPrefix(strs));
        System.out.println('c' - 'a');
    }

    /**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     * 示例 1：
     *
     * 输入：strs = ["flower","flow","flight"]
     * 输出："fl"
     * 示例 2：
     *
     * 输入：strs = ["dog","racecar","car"]
     * 输出：""
     * 解释：输入不存在公共前缀。
     * 提示：
     *
     * 1 <= strs.length <= 200
     * 0 <= strs[i].length <= 200
     * strs[i] 仅由小写英文字母组成
     * Related Topics
     * 字典树
     * 字符串
     */
    public static String longestCommonPrefix(String[] strs) {
        String longestCommonPrefix = "";
        //第一个字符
        String oneStr = Arrays.stream(strs).min(Comparator.comparingInt(String::length))
                .orElse(strs[0]);
        char[] oneChars = oneStr.toCharArray();
        for (int i = 0;i < oneChars.length;i++){
            char oneChar = oneChars[i];
            for (int j = 0;j < strs.length;j++){
                char[] chars = strs[j].toCharArray();
                char aChar = chars[i];
                if (oneChar != aChar){
                    return longestCommonPrefix;
                }
            }
            longestCommonPrefix = longestCommonPrefix + oneChar;
        }
        return longestCommonPrefix;
    }

    /**
     * 纵向比较
     */
    public static String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0){
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0;i < length;i++){
            char c = strs[0].charAt(i);
            for (int j = 0;j < count;j++){
                if (i == strs[j].length() || strs[j].charAt(i) != c){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }

    /**
     * 分治法
     */
    public static String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0){
            return "";
        } else {
            return longestCommonPrefix2(strs,0,strs.length - 1);
        }
    }

    public static String longestCommonPrefix2(String[] strs, int start, int end) {
        if (start == end){
            return strs[start];
        } else {
            int mid = (end - start) / 2 + start;
            String lcpLeft = longestCommonPrefix2(strs,start,mid);
            String lcpRight = longestCommonPrefix2(strs,mid + 1,end);
            return commonPrefix(lcpLeft,lcpRight);
        }
    }

    public static String commonPrefix(String lcpLeft,String lcpRight){
        int minLength = Math.min(lcpLeft.length(),lcpRight.length());
        for (int i = 0;i < minLength;i++){
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)){
                return lcpLeft.substring(0,i);
            }
        }
        return lcpLeft.substring(0,minLength);
    }

    /**
     * 字典树
     */
    public static String longestCommonPrefix3(String[] strs) {
        return null;
    }
}

//字典树
class DictionaryTree{
    //前缀树节点
    class TreeNode{
        TreeNode[] kids;//子节点
        boolean word = false;
        public TreeNode(){
            kids = new TreeNode[26];
        }
    }
    TreeNode root = new TreeNode();
    public String replaceWords(List<String> dictionary,String sentence){
        String[] dicts = dictionary.toArray(new String[dictionary.size()]);
        String[] words = sentence.split(" ");
        for (String s : dicts){
            buildTree(s);//建立前缀树
        }
        StringBuilder sb = new StringBuilder();
        for (String s : words){
            sb.append(find(s));//寻找符合预期的前缀单词
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    //构建树
    private void buildTree(String s){
        char[] cs = s.toCharArray();
        TreeNode node = root;
        for (char c : cs) {
            if (node.kids[c - 'a'] == null){
                //若是该节点为空，则为他分配一个孩子节点
                node.kids[c - 'a'] = new TreeNode();
            }
            //当前节点指向下一个目标节点
            node = node.kids[c - 'a'];
        }
        node.word = true;
    }

    private String find(String s){
        char[] cs = s.toCharArray();
        TreeNode node = root;
        int p = 0;
        for (char c : cs){
            //前缀树结束单词最后一个字母，返回s[0,p)即可
            if (node.word == true){
                return s.substring(0,p);
            }
            if (node.kids[c - 'a'] == null){
                return s;
            }
            node = node.kids[c - 'a'];
            p++;
        }
        return s.substring(0,p);
    }
}

class Tire{

    private Tire[] children;

    private boolean isWord;

    public Tire(){
        this.isWord = false;
        this.children = new Tire[26];
    }

    public void insert(String word){
        Tire next = this;
        for (char c : word.toCharArray()){
            if (next.children[c - 'a'] == null){
                next.children[c - 'a'] = new Tire();
            }
            next = next.children[c - 'a'];
        }
        next.isWord = true;
    }

    public boolean search(String word){
        Tire next = this;
        for (char c : word.toCharArray()){
            if (next.children[c - 'a'] == null){
                return false;
            }
            next = next.children[c - 'a'];
        }
        return next.isWord;
    }

    public boolean startsWith(String prefix){
        Tire next = this;
        for (char c : prefix.toCharArray()){
            if (next.children[c - 'a'] == null){
                return false;
            }
            next = next.children[c - 'a'];
        }
        return true;
    }
}